/*
Source : https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
Author : nflush@outlook.com
Date   : 2016-07-05
*/

/*
109. Convert Sorted List to Binary Search Tree
Total Accepted: 74364 Total Submissions: 239488 Difficulty: Medium

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Subscribe to see which companies asked this question
Have you met this question in a real interview?
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode * setTreeNode(TreeNode **all, int low, int high){
        if (low > high) return NULL;
        int mid = (high - low + 1)/2 + low;
        all[mid]->left = setTreeNode(all, low, mid-1);
        all[mid]->right = setTreeNode(all, mid+1, high);
        return all[mid];
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        int count;
        ListNode *cur;
        if (!head) return NULL;
        for (count = 0,cur = head; cur; cur=cur->next, count++);
        TreeNode *th;
        TreeNode **all = new TreeNode*[count];
        int max = count;
        for (count = 0,cur = head; cur; cur=cur->next, count++){
            all[count] = new TreeNode(cur->val);
        }
        th = setTreeNode(all, 0, count-1);
        delete [] all;
        return th;
    }
};

class Solution 
{
private:
    TreeNode* sortedListToBST(int low, int high, ListNode*& head) {
        if (low>high || head==NULL) return NULL;

        int mid = low + (high - low)/2;

        TreeNode* leftNode = sortedListToBST(low, mid-1, head);

        TreeNode* node = new TreeNode(head->val);
        node->left = leftNode;
        head = head->next;

        TreeNode* rightNode = sortedListToBST(mid+1, high, head);
        node->right = rightNode;

        return node;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) 
    {
        int len = 0;
        
        for(ListNode* p=head; p!=NULL; p=p->next){
            len++;
        }
        return sortedListToBST(0, len-1, head);
    }
};
